import java.util.*;

//方法二:不使用map来做,用两个arrayList来存他们的关系最后连接在一起
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


class MyCompare implements Comparator<Map.Entry<String, Integer>> {
    @Override
    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
        int val=o1.getValue()-o2.getValue();
        if(val!=0) return val;
        else {
            return o2.getKey().compareTo(o1.getKey());
        }
    }
}
public class Solution {
    //随机链表的复制
    //方法一：用arrayList存关系
    public Node copyRandomList1(Node head) {
        if(head==null) return null;
        ArrayList<Node> arrayList1=new ArrayList<>();
        ArrayList<Node> arrayList2=new ArrayList<>();
        Node cur=head;
        while(cur!=null) {
            arrayList1.add(cur);
            Node node=new Node(cur.val);
            arrayList2.add(node);
            cur=cur.next;
        }
        cur=head;
        int i=0;
        while(cur!=null) {
            int index=findI(cur, arrayList1);
            if(cur.next!=null)
                arrayList2.get(i).next=arrayList2.get(i+1);
            else arrayList2.get(i).next=null;
            if(index==-1) arrayList2.get(i).random=null;
            else
                arrayList2.get(i).random=arrayList2.get(index);
            i++;
            cur=cur.next;
        }
        return arrayList2.get(0);
    }
    private int findI(Node cur,ArrayList<Node> list) {
        for(int i=0;i<list.size();i++) {
            if(list.get(i)==cur.random) {
                return i;
            }
        }
        return -1;
    }
    //方法二：使用map来做K：原   V：新
    public Node copyRandomList2(Node head) {

        Map<Node, Node> map=new HashMap<>();

        Node cur=head;

        while(cur!=null) {

            Node node=new Node(cur.val);

            map.put(cur, node);

            cur=cur.next;

        }

        cur=head;

        while(cur!=null) {

            map.get(cur).next=map.get(cur.next);

            map.get(cur).random=map.get(cur.random);

            cur=cur.next;

        }

        return map.get(head);

    }
    //方法三：在原链表上做
    //随机链表不用map做
    //1 .在原链表后面插入一个值相等的节点
    //2 .给原链表中的每个新节点random填上
    //3 .将新节点拆下来，即是修改链表中每个节点的next，保证原链表要不能变化
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        Node cur=head;
        //1 .在原链表后面插入一个值相等的节点
        while(cur!=null){
            Node node=new Node(cur.val);
            node.next=cur.next;
            cur.next=node;
            cur=cur.next.next;
        }
        // 2 .给新节点random填上
        Node pre=head;
        cur=head.next;
        while(pre!=null){
            if(pre.random!=null)
                cur.random=pre.random.next;
            pre=cur.next;
            if(pre!=null)
                cur=pre.next;

        }
        //3 .将新节点拆下来，即是修改链表中每个节点的next，保证原链表要不能变化
        pre=head;
        cur=head.next;
        Node newHead=cur;
        while(pre!=null){
            pre.next=cur.next;
            if(cur.next!=null)
                cur.next=pre.next.next;
            pre=pre.next;
            cur=cur.next;
        }
        return newHead;

    }


    //前k个高频单词
    public List<String> topKFrequent(String[] words, int k) {
        List<String> list=new LinkedList<>();
        Map<String, Integer> map=new HashMap<>();
        //先用map来统计每个单词出现的频率
        for(int i=0;i<words.length;i++) {
            if(!map.containsKey(words[i])) {
                map.put(words[i], 1);
            }else {
                int old=map.get(words[i]);
                map.put(words[i], old+1);
            }
        }
        //用top-k来解决
        Set<Map.Entry<String, Integer>> set=map.entrySet();
        MyCompare myCompare=new MyCompare();
        PriorityQueue<Map.Entry<String, Integer>> priorityQueue=new PriorityQueue<>(myCompare);
        int i=0;
        for(Map.Entry<String, Integer> entry:set) {
            if(i<k) {
                priorityQueue.offer(entry);
                i++;
            }else{
                int m=myCompare.compare(entry, priorityQueue.peek());
                if(m>0) {
                    priorityQueue.poll();
                    priorityQueue.offer(entry);
                }
            }

        }
        while(!priorityQueue.isEmpty()) {
            list.add(priorityQueue.poll().getKey());
        }
        int left=0;
        int right=list.size()-1;
        while(left<right) {
            String temp =list.get(left);
            list.set(left, list.get(right));
            list.set(right, temp);
            left++;
            right--;
        }
        return list;
    }


    //宝石与石头
    //方法一：不用set直接判断，因为str1中不会重复
    public int numJewelsInStones(String str1, String str2) {
            int count=0;
            for(int i=0;i<str1.length();i++) {
                char a=str1.charAt(i);
                for(int j=0;j<str2.length();j++) {
                    if(a==str2.charAt(j)) count++;
                }
            }
            return count;
    }
    //方法二：使用set
    public int numJewelsInStones1(String str1, String str2) {
        Set<Character> set=new HashSet<Character>();
        for(int i=0;i<str1.length();i++) {
            set.add(str1.charAt(i));
        }
        int count=0;
        for(int i=0;i<str2.length();i++) {
            char a=str2.charAt(i);
            if(set.contains(a)) count++;
        }
        return count;
    }


    //只出现一次的数字
    //方法一：利用a^a=0  0^a=a来做
    public int singleNumber(int[] arr) {
        int sum=0;
        for(int i=0;i<arr.length;i++) {
            sum^=arr[i];
        }
        return sum;
    }
    //方法二：使用set来做
    public int singleNumber1(int[] arr) {
        Set<Integer> set=new HashSet<>();
        for(int i=0;i<arr.length;i++) {
            if(!set.contains(arr[i])) {
                set.add(arr[i]);
            }else {
                set.remove(arr[i]);
            }
        }
        for(Integer a:set) {
            return a;
        }
        return -1;
    }


    //存在重复数字
    //方法一：将他排序后比较
    public boolean containsDuplicate(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i <arr.length-1 ; i++) {
            if(arr[i]==arr[i+1]) return  true;
        }
        return false;
    }
    //方法二：用set来做
    public boolean containsDuplicate1(int[] arr) {
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i <arr.length ; i++) {
            if(set.contains(arr[i])) return  true;
            set.add(arr[i]);
        }
        return  false;
    }

    //方法三：计数法(会超时)
    public boolean containsDuplicate2(int[] arr) {
        int max=arr[0];
        int min=arr[0];
        for (int i = 1; i <arr.length ; i++) {
            if(min>arr[i]) min=arr[i];
            if(max<arr[i]) max=arr[i];
        }
        int[] count=new int[max-min+1];
        for (int i = 0; i <arr.length ; i++) {
            int index=arr[i]-min;
            count[index]++;
        }
        for (int i = 0; i <count.length ; i++) {
            if(count[i]==1) return true;
        }
        return  false;
    }


    //存在重复的数字2
    //方法一：双重循环（会超出时间限制）
    public boolean containsNearbyDuplicate(int[] arr, int k) {
            for (int i = 0; i <arr.length ; i++) {
                int min=-1;
                for (int j = i+1; j <arr.length ; j++) {
                    if(arr[i]==arr[j]) {
                        min=Math.abs(i-j);
                        if(min<=k) return true;
                    }
                }
            }
            return false;
    }
    //方法二：用map去做,思路就  1.用mapK:用来存arr【i】的值 V:用来存他的下标  2. 在遍历过程中map没有将其添加进入map
    //                      3.map中有的话，先不添加，先取用map.get()取出上一个下标为j，用现在的下标i-j（后面的i一定比j大）
    //                        判断是否小于k，小于等于返回true，否则的话map.put更新当前值的下标往后走，最后遍历完成没有返回true，即返回false不存在
    public boolean containsNearbyDuplicate1(int[] arr, int k) {
        //K:用来存arr【i】的值 V:用来存他的下标
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if(!map.containsKey(arr[i])){
                map.put(arr[i],i);
            }else{
                int j=map.get(arr[i]);
                if(i-j<=k) return true;
                else{
                    map.put(arr[i],i);
                }
            }
        }
        return false;
    }

}


